package leetcode_0020

/**
 * 有效的括号（包括括号以及普通字符）
 * 利用堆栈的特性，先进后出，与括号的匹配规则相同
 */
func isValid1(s string) bool {

	var tmpStack []byte
	tmpMap1 := map[byte]byte{'(': ')', '[': ']', '{': '}'}
	tmpMap2 := map[byte]byte{')': '(', ']': '[', '}': '{'}
	for i := 0; i < len(s); i++ {
		// 入栈
		if _, ok := tmpMap1[s[i]]; ok {
			tmpStack = append(tmpStack, s[i])
			continue
		}

		// 出栈
		if _, ok := tmpMap2[s[i]]; ok {
			if len(tmpStack) > 0 && tmpMap2[s[i]] == tmpStack[len(tmpStack)-1] {
				tmpStack = tmpStack[:len(tmpStack)-1]
				continue
			}

			return false
		}
	}

	// 判断栈内是否还有元素
	if len(tmpStack) > 0 {
		return false
	}

	return true
}

/**
 * 有效的括号（只包含括号）
 * 利用堆栈的特性，先进后出，与括号的匹配规则相同
 */
func isValid2(s string) bool {
	var tmpStack []byte
	tmpMap := map[byte]byte{')': '(', ']': '[', '}': '{'}
	for i := 0; i < len(s); i++ {
		// 入栈
		if _, ok := tmpMap[s[i]]; !ok {
			tmpStack = append(tmpStack, s[i])
		} else { // 出栈
			if len(tmpStack) == 0 || tmpMap[s[i]] != tmpStack[len(tmpStack)-1] {
				return false
			}
			tmpStack = tmpStack[:len(tmpStack)-1]
		}
	}

	// 判断栈内是否还有元素
	if len(tmpStack) > 0 {
		return false
	}

	return true
}
